home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / nt / source.exe / POSIX / FIND / OPERATOR.C < prev    next >
C/C++ Source or Header  |  1992-10-29  |  8KB  |  299 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Cimarron D. Taylor of the University of California, Berkeley.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #ifndef lint
  38. static char sccsid[] = "@(#)operator.c    5.4 (Berkeley) 5/24/91";
  39. #endif /* not lint */
  40.  
  41. #if DF_POSIX
  42. # include <misc.h>
  43. #endif
  44.  
  45. #include <sys/types.h>
  46. #include <sys/stat.h>
  47. #include <stdio.h>
  48. #include "find.h"
  49.  
  50. #if WIN_NT
  51. extern int f_expr (PLAN *, FTSENT *);
  52. #endif
  53.     
  54. /*
  55.  * yanknode --
  56.  *    destructively removes the top from the plan
  57.  */
  58. static PLAN *
  59. #if __STDC__
  60. yanknode (PLAN **planp)    
  61. #else
  62. yanknode(planp)    
  63.     PLAN **planp;        /* pointer to top of plan (modified) */
  64. #endif
  65. {
  66.     PLAN *node;        /* top node removed from the plan */
  67.     
  68.     if ((node = (*planp)) == NULL)
  69.         return(NULL);
  70.     (*planp) = (*planp)->next;
  71.     node->next = NULL;
  72.     return(node);
  73. }
  74.  
  75. /*
  76.  * yankexpr --
  77.  *    Removes one expression from the plan.  This is used mainly by
  78.  *    paren_squish.  In comments below, an expression is either a
  79.  *    simple node or a N_EXPR node containing a list of simple nodes.
  80.  */
  81. static PLAN *
  82. #if __STDC__
  83. yankexpr (PLAN **planp)    
  84. #else
  85. yankexpr(planp)    
  86.     PLAN **planp;        /* pointer to top of plan (modified) */
  87. #endif
  88. {
  89.     register PLAN *next;    /* temp node holding subexpression results */
  90.     PLAN *node;        /* pointer to returned node or expression */
  91.     PLAN *tail;        /* pointer to tail of subplan */
  92.     PLAN *subplan;        /* pointer to head of ( ) expression */
  93. #if !WIN_NT
  94.     int f_expr();
  95. #endif
  96.     
  97.     /* first pull the top node from the plan */
  98.     if ((node = yanknode(planp)) == NULL)
  99.         return(NULL);
  100.     
  101.     /*
  102.      * If the node is an '(' then we recursively slurp up expressions
  103.      * until we find its associated ')'.  If it's a closing paren we
  104.      * just return it and unwind our recursion; all other nodes are
  105.      * complete expressions, so just return them.
  106.      */
  107.     if (node->type == N_OPENPAREN)
  108.         for (tail = subplan = NULL;;) {
  109.             if ((next = yankexpr(planp)) == NULL)
  110.                 err("%s: %s", "(", "missing closing ')'");
  111.             /*
  112.              * If we find a closing ')' we store the collected
  113.              * subplan in our '(' node and convert the node to
  114.              * a N_EXPR.  The ')' we found is ignored.  Otherwise,
  115.              * we just continue to add whatever we get to our
  116.              * subplan.
  117.              */
  118.             if (next->type == N_CLOSEPAREN) {
  119.                 if (subplan == NULL)
  120.                     err("%s: %s",
  121.                         "()", "empty inner expression");
  122.                 node->p_data[0] = subplan;
  123.                 node->type = N_EXPR;
  124.                 node->eval = f_expr;
  125.                 break;
  126.             } else {
  127.                 if (subplan == NULL)
  128.                     tail = subplan = next;
  129.                 else {
  130.                     tail->next = next;
  131.                     tail = next;
  132.                 }
  133.                 tail->next = NULL;
  134.             }
  135.         }
  136.     return(node);
  137. }
  138.  
  139. /*
  140.  * paren_squish --
  141.  *    replaces "parentheisized" plans in our search plan with "expr" nodes.
  142.  */
  143. PLAN *
  144. #if __STDC__
  145. paren_squish (PLAN *plan)
  146. #else
  147. paren_squish(plan)
  148.     PLAN *plan;        /* plan with ( ) nodes */
  149. #endif
  150. {
  151.     register PLAN *expr;    /* pointer to next expression */
  152.     register PLAN *tail;    /* pointer to tail of result plan */
  153.     PLAN *result;        /* pointer to head of result plan */
  154.     
  155.     result = tail = NULL;
  156.  
  157.     /*
  158.      * the basic idea is to have yankexpr do all our work and just
  159.      * collect it's results together.
  160.      */
  161.     while ((expr = yankexpr(&plan)) != NULL) {
  162.         /*
  163.          * if we find an unclaimed ')' it means there is a missing
  164.          * '(' someplace.
  165.          */
  166.         if (expr->type == N_CLOSEPAREN)
  167.             err("%s: %s", ")", "no beginning '('");
  168.  
  169.         /* add the expression to our result plan */
  170.         if (result == NULL)
  171.             tail = result = expr;
  172.         else {
  173.             tail->next = expr;
  174.             tail = expr;
  175.         }
  176.         tail->next = NULL;
  177.     }
  178.     return(result);
  179. }
  180.  
  181. /*
  182.  * not_squish --
  183.  *    compresses "!" expressions in our search plan.
  184.  */
  185. PLAN *
  186. #if __STDC__
  187. not_squish (PLAN *plan)
  188. #else
  189. not_squish(plan)
  190.     PLAN *plan;        /* plan to process */
  191. #endif
  192. {
  193.     register PLAN *next;    /* next node being processed */
  194.     register PLAN *node;    /* temporary node used in N_NOT processing */
  195.     register PLAN *tail;    /* pointer to tail of result plan */
  196.     PLAN *result;        /* pointer to head of result plan */
  197.     
  198.     tail = result = next = NULL;
  199.     
  200.     while ((next = yanknode(&plan)) != NULL) {
  201.         /*
  202.          * if we encounter a ( expression ) then look for nots in
  203.          * the expr subplan.
  204.          */
  205.         if (next->type == N_EXPR)
  206.             next->p_data[0] = not_squish(next->p_data[0]);
  207.  
  208.         /*
  209.          * if we encounter a not, then snag the next node and place
  210.          * it in the not's subplan.  As an optimization we compress
  211.          * several not's to zero or one not.
  212.          */
  213.         if (next->type == N_NOT) {
  214.             int notlevel = 1;
  215.  
  216.             node = yanknode(&plan);
  217.             while (node->type == N_NOT) {
  218.                 ++notlevel;
  219.                 node = yanknode(&plan);
  220.             }
  221.             if (node == NULL)
  222.                 err("%s: %s", "!", "no following expression");
  223.             if (node->type == N_OR)
  224.                 err("%s: %s", "!", "nothing between ! and -o");
  225.             if (notlevel % 2 != 1)
  226.                 next = node;
  227.             else
  228.                 next->p_data[0] = node;
  229.         }
  230.  
  231.         /* add the node to our result plan */
  232.         if (result == NULL)
  233.             tail = result = next;
  234.         else {
  235.             tail->next = next;
  236.             tail = next;
  237.         }
  238.         tail->next = NULL;
  239.     }
  240.     return(result);
  241. }
  242.  
  243. /*
  244.  * or_squish --
  245.  *    compresses -o expressions in our search plan.
  246.  */
  247. PLAN *
  248. #if __STDC__
  249. or_squish (PLAN *plan)
  250. #else
  251. or_squish(plan)
  252.     PLAN *plan;        /* plan with ors to be squished */
  253. #endif
  254. {
  255.     register PLAN *next;    /* next node being processed */
  256.     register PLAN *tail;    /* pointer to tail of result plan */
  257.     PLAN *result;        /* pointer to head of result plan */
  258.     
  259.     tail = result = next = NULL;
  260.     
  261.     while ((next = yanknode(&plan)) != NULL) {
  262.         /*
  263.          * if we encounter a ( expression ) then look for or's in
  264.          * the expr subplan.
  265.          */
  266.         if (next->type == N_EXPR)
  267.             next->p_data[0] = or_squish(next->p_data[0]);
  268.  
  269.         /* if we encounter a not then look for not's in the subplan */
  270.         if (next->type == N_NOT)
  271.             next->p_data[0] = or_squish(next->p_data[0]);
  272.  
  273.         /*
  274.          * if we encounter an or, then place our collected plan in the
  275.          * or's first subplan and then recursively collect the
  276.          * remaining stuff into the second subplan and return the or.
  277.          */
  278.         if (next->type == N_OR) {
  279.             if (result == NULL)
  280.                 err("%s: %s", "-o", "no expression before -o");
  281.             next->p_data[0] = result;
  282.             next->p_data[1] = or_squish(plan);
  283.             if (next->p_data[1] == NULL)
  284.                 err("%s: %s", "-o", "no expression after -o");
  285.             return(next);
  286.         }
  287.  
  288.         /* add the node to our result plan */
  289.         if (result == NULL)
  290.             tail = result = next;
  291.         else {
  292.             tail->next = next;
  293.             tail = next;
  294.         }
  295.         tail->next = NULL;
  296.     }
  297.     return(result);
  298. }
  299.